package Year22_Month07.day07;

public class 堆排序 {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    public void heapSort(int[] nums){
        int size = nums.length;
        for (int i = (size - 1)/2; i >= 0; i--) {
            shiftdown(nums,size,i);
        }
        int index = nums.length - 1;
        while(index > 0){
            swap(nums,index,0);
            shiftdown(nums,index,0);
            index--;
        }
    }

    public void shiftdown(int[] nums,int size,int parent){
        int child = parent * 2 + 1;
        while(child < size){
            if(child + 1 < size && nums[child] < nums[child + 1]){
                child = child + 1;
            }

            if(nums[parent] > nums[child]){
                swap(nums,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }

        }
    }

    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
